package com.fmm.medium;

import java.util.PriorityQueue;

public class MinRefuelingCount {

    /**
     * @param target 目标距离
     * @param startFuel 起始油量
     * @param stations 加油站信息，每一个加油站信息为[距离最开始起点的距离, 加油站的油量]
     * @return 最少加油次数
     * */
    public static int minRefuelStops(int target, int startFuel, int[][] stations) {
        // 保存最终加油次数
        int count = 0;
        // maxLength 表示当前油量可到达的最远距离，初始值为汽车本身带有的油量
        int maxLength = startFuel;
        // 保存每个加油站油量，并从大到小排列
        PriorityQueue<Integer> stationFuelKeeping = new PriorityQueue<>((a, b) -> b - a);
        // 遍历加油站信息
        for (int[] station : stations) {
            if (maxLength >= target) {
                return count;
            }
            // 当前油量到不了下一个加油站时，从前面已经路过的加油站中选择最大的站加油
            while (maxLength < station[0]) {
                Integer maxFuel = stationFuelKeeping.poll();
                // 路过的加油站全部都加油都到不了，返回-1
                if (maxFuel == null) {
                    return -1;
                }
                maxLength = maxLength + maxFuel;
                count++;
            }
            stationFuelKeeping.offer(station[1]);
        }

        // 目标距离比加油站要远，处理从最后一个加油站到目的地这段距离是否够
        while (maxLength < target) {
            Integer maxFuel = stationFuelKeeping.poll();
            if (maxFuel == null) {
                return -1;
            }
            maxLength = maxLength + maxFuel;
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int target = 100;
        int startFuel = 10;
        int[][] stations = new int[][]{{10,60},{20,30},{30,30},{60,40}};
        System.out.println(minRefuelStops(target, startFuel, stations));
    }
}
